package com.zxlfysj.dijkstra;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法实例
 *
 * @author yangshujing
 * @create 2020-08-26 17:27
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();
        graph.dsj(6);
        graph.show();
    }
}

class Graph {
    private char[] vertex; //顶点数组
    private int[][] matrix; //邻接矩阵
    private VisitedVertex visitedVertex;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    //显示图的邻接矩阵
    public void showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    //迪杰斯特拉算法实现
    public void dsj(int index) {
        visitedVertex = new VisitedVertex(vertex.length, index);
        update(index);
        for(int j = 1; j < vertex.length; j++) {
            index = visitedVertex.updateArr();
            update(index);
        }

    }

    //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
    public void update(int index) {
        int len = 0;
        //遍历邻接矩阵的matrix[index]
        for(int j = 0; j < matrix[index].length; j++) {
            //出发顶点到index的距离 + 从index到j顶点的距离
            len = visitedVertex.getDis(index) + matrix[index][j];
            //如果未访问过的顶点，并且通过index中间节点访问的路径比直接访问短，
            // 则更新前驱结点和距离
            if(!visitedVertex.isVisited(j) && len < visitedVertex.getDis(j)) {
                visitedVertex.updatePre(j, index);
                visitedVertex.updateDis(j, len);
            }
        }
    }

    //输出最后结果
    public void show() {
        visitedVertex.show(vertex);
    }
}

class VisitedVertex {
    public int[] already_arr; //记录各个顶点是否访问过，1=访问过，0=未访问
    public int[] pre_visited; //记录前一个顶点的下标
    public int[] dis;   //记录出发顶点到其他顶点的距离

    /**
     * 构造器
     *
     * @param length 顶点的个数
     * @param index  出发顶点的下标
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        Arrays.fill(dis, 65535);
        this.already_arr[index] = 1;
        this.dis[index] = 0;
    }

    /**
     * 判断index的顶点是否被访问过
     *
     * @param index
     * @return
     */
    public boolean isVisited(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     *
     * @param index
     * @param len
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 更新pre这个顶点的前驱顶点为index顶点
     *
     * @param pre
     * @param index
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

    /**
     * 返回出发顶点到index顶点的距离
     *
     * @param index
     * @return
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 继续选择新的访问顶点
     * @return
     */
    public int updateArr() {
        int min = 65535;
        int index = 0;
        for(int i = 0; i < already_arr.length; i++) {
            //选择还没访问过的最短路径的那个顶点
            if(already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index= i;
            }
        }
        already_arr[index] = 1;
        return index;
    }

    //输出最后的结果
    public void show(char[] vertex) {
        int count = 0;
        for(int i : dis) {
            if(i != 65535) {
                System.out.println(vertex[count] + "(" + i + ")");
            } else {
                System.out.println("N ");
            }
            count++;
        }
    }
}
